package com.example.question.dp.dp4;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Date 2023-07-29
 * @Author Jonathan
 */
public class Code07_354 {
    public static void main(String[] args) {
        Code07_354 code = new Code07_354();
        int[][] ints = new int[][]{{5, 4}, {6, 7}, {6, 4}, {2, 3}};
        int i = code.maxEnvelopes(ints);
        System.out.println(i);
    }

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, Comparator.comparingInt(ints2 -> ints2[0]));
        return dfs(envelopes, 0, 0, 0, new Integer[envelopes.length]);
    }

    /**
     * 超出时间限制 需要优化成动态规划
     */
    private int dfs(int[][] envelopes, int index, int width, int height, Integer[] memo) {
        if (index >= envelopes.length) {
            return 0;
        }
        if (memo[index] != null) {
            return memo[index];
        }
        int res = 0;
        for (int i = index; i < envelopes.length; i++) {
            if (envelopes[i][0] <= width || envelopes[i][1] <= height) {
                continue;
            }
            int dfs = dfs(envelopes, i + 1, envelopes[i][0], envelopes[i][1], memo);
            res = Math.max(res, dfs + 1);
        }
        memo[index] = res;
        return memo[index];
    }


}
